#coding: utf-8 

from copy import *
from matrix import *

from simData import *

from worldPath import *
from visionSegmentation import unite



def connected(pos0,pos1):
	return pos0.dist_to(pos1)<=dist*1.01

def getNumberedAreas(area):
	
	areas={}
	for value,x,y in area:
		if(value!=0):
			try:
				areas[value-1].setitem(x,y,1)
			except:
				areas[value-1]=Area(area.scale,area.left,area.bot)
				areas[value-1].setitem(x,y,1)
	
	for a in areas.values():
		a.clear()
	return areas


class Area(Matrix):
	def __init__(self,scale,left,bot): 
		# Import Psyco if available
		try:
			import psyco
			psyco.full()
		except ImportError:
			pass
			
		psyco.log()
		psyco.profile(0.05)
		
		Matrix.__init__(self)
		self.scale=scale #scale=0.40m 
		self.left=left
		self.bot=bot
		self.positionsOrdS={}
		self.positionsOrdCirc={}
		self.paths={}
		
	@property
	def center(self):
		totalx=0
		totaly=0
		totalPoints=0
		
		for value,x,y in self:
			if value ==True:
				pos=self.getPosition(x,y)
				totalPoints+=1
				totalx+=pos.x
				totaly+=pos.y
		
		try:
			return Position(totalx/totalPoints,totaly/totalPoints)
		except:
			return Position(self.left,self.bot)
		
	def clear(self):
		minx=''
		maxx=None
		miny=''
		maxy=None
		
		for value,x,y in self:
			if value==True:
				if x<minx: minx=x
				if x>maxx: maxx=x
				if y<miny: miny=y
				if y>maxy: maxy=y

		if(minx == ''): return
		for x in range(0,minx,1):
			self.popcol(0)
			self.left+=self.scale
		for x in range(maxx,self.xMax-1,1):
			self.popcol(maxx)
		
		for y in range(0,miny,1):
			self.poprow(0)
			self.bot+=self.scale
		for y in range(maxy,self.yMax-1,1):
			self.popcol(maxy)
		
	def getSlice(self,xmin=0,xmax=None,ymin=0,ymax=None):
		if xmax==None:
			xmax=self.xMax
		if ymax==None:
			ymax=self.yMax
		
		slicedArea=Area(self.scale,self.left,self.bot)
		
		for value,x,y in self:
			if xmin<=x<xmax and ymin<=y<ymax:
				slicedArea.setitem(x,y,value)
		return slicedArea
		
	
	
	def cellDecomp(self):
		#procurar linhas divisorias horizontais
		hLines=[0]
		for y in range(1,self.yMax):
			for x in range(self.xMax):
				itemTop=self.getitem(x,y-1)
				itemBot=self.getitem(x,y)
				if itemBot != itemTop:
					hLines.append(y)
					break
		hLines.append(self.yMax)
		
		#procurar linhas divisorias verticais
		vLines=[0]
		for x in range(1,self.xMax):
			for y in range(self.yMax):
				itemLeft=self.getitem(x-1,y)
				itemRight=self.getitem(x,y)
				if itemLeft != itemRight:
					vLines.append(x)
					break
		vLines.append(self.xMax)
		
		#partir áreas
		def getSliceNumber(x,y):
			if x>=self.xMax or x<0 or y>=self.yMax or y<0:
				return None
			else:
				for vi in range(len(vLines)-1):
					if vLines[vi]<=x<vLines[vi+1]:
						for hi in range(len(hLines)-1):
							if hLines[hi]<=y<hLines[hi+1]:
								return hi*len(vLines)+vi+1
		
		tArea=deepcopy(self)
		
		for value,x,y in self:
			if value==1:
				tArea.setitem(x,y,getSliceNumber(x,y))
		
		#agregar áreas
		#agregar horizontais
		def agreg(mask,victim):
			for value,x,y in tArea:
				if value==victim:
					tArea.setitem(x,y,mask)
		
		for hLine in hLines[1:-1]:
			init = True
			(refTop,refBot) = (None,None)
			(lastTop,lastBot) = (None,None)
			(top,bot) = (None,None)
			for x in range(self.xMax):
				(lastTop,lastBot) = (top,bot)
				top,bot=tArea.getitem(x,hLine),tArea.getitem(x,hLine-1)
				if not init:
					if top!=refTop and bot!=refBot:
						#são agregáveis
						agreg(refTop,refBot)
						init = True
					elif top!=refTop or bot!=refBot:
						init = True
				
				if init:
					if 0 not in [top,bot] and lastTop!=top and lastBot!=bot:
						init = False
						(refTop,refBot)=(top,bot)
			if not init:
				agreg(refTop,refBot)

		#agregar verticais
		for vline in vLines[1:-1]:
			init = True
			(refRight,refLeft) = (None,None)
			(lastRight,lastLeft) = (None,None)
			(Right,Left) = (None,None)
			for y in range(self.yMax):
				(lastRight,lastLeft) = (Right,Left) 
				Right,Left=tArea.getitem(vline,y),tArea.getitem(vline-1,y)
				if not init:
					if Right!=refRight and Left!=refLeft:
						#são agregáveis
						agreg(refRight,refLeft)
						init = True
					elif Right!=refRight or Left!=refLeft:
						init = True
				if init:
					if 0 not in [Right,Left] and lastRight != Right and lastLeft != Left:
						init = False
						(refRight,refLeft)=(Right,Left)
			if not init:
				agreg(refRight,refLeft)
		
		numbers=[0]
		for value,x,y in tArea:
			if value not in numbers:
				numbers.append(value)
		numbers.sort()
		
		etiquetas={}
		for i in range(len(numbers)):
			etiquetas[numbers[i]]=i
		etiquetas[0]=0
		
		for value,x,y in tArea:
			tArea.setitem(x,y,etiquetas[value])
		
		self.numbers=tArea
		return getNumberedAreas(tArea)
		
		
	def cellDecomp2(self):
		#~ import time
		#~ time0=time.time()
		
	#--------------------------------------------
		# 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1
	#-----------X-X-X-----------------X-X-X------
		# 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
	#			   ------------X-X-X-----X-X----
		# 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1
	#-------------X-------------------X-X--------
		# 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1
	#
		# 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0
	#-------------------------------X-----X------
		# 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
	#
		# 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
	#
		#conclusão:
		#	procurar 0s com uns dos lados e em baixo ou em cima
		#	procurar 1s com uns dos lados e em baixo ou em cima
		
		lines=[0]
		# procura linhas para separação de slices
		for y in range(0,self.yMax-1):
			zeros=True
			ones=True
			discard=True
			for x in range(0,self.xMax-1):
				item=self.getitem(x,y)
				
				if (discard):
					if item==0:
						if not zeros:
							zeros=True
							ones=False
							discard=False
						else:
							zeros=True
							ones=False
							discard=True
					elif item==1:
						if not ones:
							ones=True
							zeros=False
							discard=False
						else:
							ones=True
							zeros=False
							discard=True
					else:
						print 'item <> 0 ?!'
						print item
				if (not discard):
					itemUP=self.getitem(x,y+1)
					if zeros:
						discard=(itemUP==0)
					if ones:
						discard=(itemUP==1)
				if (not discard):
					itemRIGHT=self.getitem(x+1,y)
					if (zeros and itemRIGHT==1) or (ones and itemRIGHT==0):
						lines.append(y+1)
						break
		lines.append(self.yMax)
		
		#search down
		for y in range(1,self.yMax):
			zeros=True
			ones=True
			discard=True
			for x in range(0,self.xMax-1):
				item=self.getitem(x,y)
				
				if (discard):
					if item==0:
						if not zeros:
							zeros=True
							ones=False
							discard=False
							
						else:
							zeros=True
							ones=False
							discard=True
					elif item==1:
						if not ones:
							ones=True
							zeros=False
							discard=False
						else:
							ones=True
							zeros=False
							discard=True
					else:
						print 'item <> 0 ?!'
						print item
				if (not discard):
					itemDOWN=self.getitem(x,y-1)
					if zeros:
						discard=(itemDOWN==0)
					if ones:
						discard=(itemDOWN==1)
				if (not discard):
					itemRIGHT=self.getitem(x+1,y)
					if (zeros and itemRIGHT==1) or (ones and itemRIGHT==0):
						lines.append(y)
						break
		
		lines.sort()
		
		slicedAreas=[]
		
		tArea=deepcopy(self)
		
		for value,x,y in self:
			if value==1:
				for i in range(len(lines)-1):
					if lines[i+1]>y:
						tArea.setitem(x,y,(i+1))
						break
		
		refuse=0
		
		etiquetas=0
		etiquetagem=[]
		
		for y in range(tArea.yMax):
			for x in range(tArea.xMax):
				item=tArea.getitem(x,y)
				if  item != refuse:
					mark=[]
					if (tArea.getitem(x-1,y)/1000==item):
						mark.append(tArea.getitem(x-1,y))
					if (tArea.getitem(x-1,y-1)/1000==item):
						mark.append(tArea.getitem(x-1,y-1))
					if (tArea.getitem(x,y-1)/1000==item):
						mark.append(tArea.getitem(x,y-1))
					if (tArea.getitem(x+1,y-1)/1000==item):
						mark.append(tArea.getitem(x+1,y-1))
					if (len(mark)==0):
						etiquetas+=1
						mark.append(etiquetas+(item*1000))
					if (len(mark)>=1):
						mark.sort()
						etiquetagem.append(mark)
						
					tArea.setitem(x,y,mark[0])
		
		etiquetagem=unite(etiquetagem)
		
		dEtiq={}
		for i in etiquetagem:
			dEtiq[len(dEtiq)+1]=i
		
		invDictEtic={}
		for name,nums in dEtiq.items():
			for num in nums:
				invDictEtic[num]=name
		
		invDictEtic[0]=0
		
		for x in range(tArea.xMax):
			for y in range(tArea.yMax):
				num=tArea.getitem(x,y)
				tArea.setitem(x,y,invDictEtic[num])
		
		self.numbers=tArea
		
		return getNumberedAreas(tArea)
		
	def getBorder(self):
		area2=Area(self.scale,self.left,self.bot)
		for value,x,y in self:
			flag = False
			for dx,dy in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
				if self.getitem(x+dx,y+dy) == False:
					flag = True
					break
			if flag:
				area2.setitem(x,y,self.getitem(x,y))
			else:
				area2.setitem(x,y,0)
		return area2
		
	def removeBorder(self):
		area2=Area(self.scale,self.left,self.bot)
		for value,x,y in self:
			flag = False
			for dx,dy in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]:
				if self.getitem(x+dx,y+dy) == False:
					flag = True
					break
			if flag:
				area2.setitem(x,y,0)
			else:
				area2.setitem(x,y,self.getitem(x,y))
		return area2
	
	def getPositions(self):
		positions=[]
		for x in range(self.xMax):
			for y in range(self.yMax):
				if self.getitem(x,y) == True:
					positions.append(self.getPosition(x+CLEANGRID/2,y+CLEANGRID/2))
		return positions
	
	def getPosition(self,x,y):
		return Position(self.left+float(x)*self.scale,self.bot+float(y)*self.scale)
	
	def getNearXYfromPosition(self,pos):
		xOfMin=None
		yOfMin=None
		minDist='None'
		
		if isinstance(pos,Position):
			for value,x,y in self:
				if value==1:
					dist=pos.dist_to(self.getPosition(x,y))
					if dist<minDist:
						minDist=dist
						xOfMin=x
						yOfMin=y
		else:
			for value,x,y in self:
				if value==1:
					p=self.getPosition(x,y)
					dist=(pos[0]-p.x)**2+(pos[1]-p.y)**2
					if dist<minDist:
						minDist=dist
						xOfMin=x
						yOfMin=y
						
		if xOfMin!=None:
			return (xOfMin,yOfMin)
		else:
			return None

	def findPath(self,fromPos,toPos):
		
		import time
		init=time.time()
		
		#inicializações
		if isinstance(fromPos,Position):
			fromPoint=self.getNearXYfromPosition(fromPos)
		else:
			fromPoint=fromPos
		if isinstance(toPos,Position):
			toPoint=self.getNearXYfromPosition(toPos)
		else:
			toPoint=toPos
		
		try:
			return self.paths[(fromPoint,toPoint)]
		except:
			pass
		
		#preparação dos outputs para o explorer
		self.values=LMatrix(self.xMax,self.yMax,None)
		self.floorInf=LMatrix(self.xMax,self.yMax,'X')
		for value,x,y in self:
			if value==1:
				self.floorInf[x][y]=1
		self.path=LMatrix(self.xMax,self.yMax,[])
		
		explorer=Explorer()
		explorer.smartExp(fromPoint,toPoint,self.values,self.floorInf,self.path,0)
		
		positions=[]
		for point in self.path[toPoint[0]][toPoint[1]]:
			positions.append(self.getPosition(point[0],point[1]))
		self.paths[(fromPoint,toPoint)]=positions
		
		return positions
		

	def genAllPositionsOrdCirc(self):
		for clockWise in (True,False):
			for bot in (True,False):
				for left in (True,False):
					self.getPositionsOrdCirc(clockWise,bot,left)
					
	def getPositionsOrdCirc(self,clockWise=True,bot=True,left=True):
		#clockwise means "always turn left"
		
		try:
			return self.positionsOrdCirc[clockWise,bot,left]
		except:
			pass
		
		tArea=deepcopy(self)
		def getxy(complex):
			return (int(complex.real), int(complex.imag))
		
		def onTrail(x,y,direction=None):
			if direction != None:
				(dx,dy)=getxy(direction)
			else:
				(dx,dy)=(0,0)
			return tArea.getitem(x+dx,y+dy) == 1 
		
		if left==True:
			xInit=0
			dx=1
		if left==False:
			xInit=self.xMax-1
			dx=-1
		if bot==True:
			yInit=0
			dy=1
		if bot==False:
			yInit=self.yMax-1
			dy=-1
		
		x=xInit
		y=yInit
		
		xInc=True
		while (not onTrail(x,y)):
			if 0<x+dx<self.xMax:
				x=x+dx
			elif 0<y+dy<self.yMax:
				x=xInit
				y=y+dy
			else:
				break
		
		#girar a esquerda = multiplicar por 1j
		if clockWise:
			turn = 1j
		else:
			turn = -1j
		
		direction=1
		count=0
		while(onTrail(x,y,direction*turn) or not onTrail(x,y,direction)):
			direction*=turn
			count+=1
			if count>5:
				return [self.getPosition(x,y)]
		
		positions=[]
		
		noWhereElseToGo=False
		lastKnownSecondOption = None
		
		count=1
		
		#find the positions
		while(not noWhereElseToGo and onTrail(x,y)):
			positions.append(self.getPosition(x,y))
			tArea.setitem(x,y,2)
			count+=1
			
			x0,y0=x,y
			if(onTrail(x,y,direction*turn)):
				direction*=turn
				(dx,dy)=getxy(direction)
				x+=dx
				y+=dy
			elif (onTrail(x,y,direction)):
				(dx,dy)=getxy(direction)
				x+=dx
				y+=dy
			elif (onTrail(x,y,direction/turn)):
				direction/=turn
				(dx,dy)=getxy(direction)
				x+=dx
				y+=dy
			else:
				if lastKnownSecondOption is None:
					noWhereElseToGo=True
				else:
					positions+=self.findPath(positions[len(positions)-1],lastKnownSecondOption)
					x,y=lastKnownSecondOption
					lastKnownSecondOption = None
					
			# Encontrar uma segunda posição viável para posteriormente voltar lá
			if onTrail(x0,y0,direction/turn):
				(dx,dy)=getxy(direction/turn)
				lastKnownSecondOption = None
				#~ lastKnownSecondOption=(x0+dx,y0+dy)
			elif onTrail(x0,y0,direction/turn/turn):
				(dx,dy)=getxy(direction/turn/turn)
				lastKnownSecondOption = None
				#~ lastKnownSecondOption=(x0+dx,y0+dy)
		
		self.positionsOrdCirc[clockWise,bot,left]=positions
		return positions
	
	def genAllPositionsOrdS(self):
		for xAxis in (True,False):
			for bot in (True,False):
				for left in (True,False):
					self.getPositionsOrdS(xAxis,bot,left)
	
	def getPositionsOrdS(self,xAxis=True,bot=True,left=True):
		"""usage: c.robot[0].addt(c.rooms[67].area.getOrdedSPositions(bot=True,left=False,xAxis=True))"""
		try:
			return self.positionsOrdS[xAxis,bot,left]
		except:
			pass
		
		def onTrail(x,y):
			return self.getitem(x,y) == 1 
		
		#inicialization
		if left==True:
			xInit=0
			dx=1
		if left==False:
			xInit=self.xMax-1
			dx=-1
		if bot==True:
			yInit=0
			dy=1
		if bot==False:
			yInit=self.yMax-1
			dy=-1

		x=xInit
		y=yInit
		
		#trailing
		while (not onTrail(x,y)):
			if xAxis:
				if 0<x+dx<self.xMax:
					x=x+dx
				elif 0<y+dy<self.yMax:
					x=xInit
					y=y+dy
				else:
					break
			else:
				if 0<y+dy<self.yMax:
					y=y+dy
				elif 0<x+dx<self.xMax:
					y=yInit
					x=x+dx
				else:
					break
					
		positions=[]
		
		jump=False #force jump to next S
		endPositions=[]
		
		noWhereElseToGo=False
		#find the positions
		while(not noWhereElseToGo and onTrail(x,y)):
			if not jump:
				positions.append(self.getPosition(x,y))
			else:
				endPositions.append(self.getPosition(x,y))
			if xAxis:
				if jump and onTrail(x,y+dy):
					y+=dy
					jump=False
					positions+=endPositions
					endPositions=[]
				elif onTrail(x+dx,y):
					x+=dx
				elif onTrail(x,y+dy):
					y+=dy
					dx=-dx
				elif not jump:
					dx=-dx
					jump=True
				else:
					noWhereElseToGo=True
			else:
				if jump and onTrail(x+dx,y):
					x+=dx
					jump=False
					positions+=endPositions
					endPositions=[]
				elif onTrail(x,y+dy):
					y+=dy
				elif onTrail(x+dx,y):
					x+=dx
					dy=-dy
				elif not jump:
					dy=-dy
					jump=True
				else:
					noWhereElseToGo=True
					
		self.positionsOrdS[xAxis,bot,left]=positions
		return positions
		
		
	def __repr__(self):
		text='(xLeft,yBot)='+str((self.left,self.bot))+' ; scale='+str(self.scale)
		text+='\n'+Matrix.__repr__(self)
		
		return text

class Explorer():
	def __init__(self):
		self.operations=0
		self.mMax=0
		self.explored=[]
		self.explode=[]
		
		
	def smartExp(self,fromPoint,toPoint,matrix,obstaculos,path,initvalue):
		self.explored=[]
		self.explore=[]
		
		x=fromPoint[0]
		y=fromPoint[1]
		xTo=toPoint[0]
		yTo=toPoint[1]
		
		p=path
		m=matrix
		ob=obstaculos
		
		try:
			m[x][y]=int(initvalue)
			self.explode.append((x,y))
			self.explored.append((x,y))
		except IndexError: #explora fora da janela
			return
		except ValueError:
			return
		
		
		
		while len(self.explode)>0:
			min = m[self.explode[0][0]][self.explode[0][1]]
			

			for x,y in self.explode:
				if m[x][y] < min:
					min=m[x][y]
			
			for x,y in self.explode:
				if min is m[x][y]:
					for i,j in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)]:
						if(x+i >= 0 and y+j>=0):
							self.explorePosition(x+i,y+j,m,ob,p)
							if (x+i==xTo and y+j==yTo): return
					self.explode.remove((x,y))
				
	def explorePosition(self,x,y,matrix,obstaculos,path):
		self.operations+=1
		p=path
		m=matrix
		ob=obstaculos
		
		try:
			value=int(ob[x][y])
		except IndexError: #explora fora da janela
			return
		except ValueError:
			return
		
		around_value=None
		around_min_path=[]
		for i,j in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)]:
			if(x+i >= 0 and y+j>=0):
				try:
					if (m[x+i][y+j] is not None) and ((around_value is None) or (m[x+i][y+j]<around_value)):
						around_value=m[x+i][y+j]
						around_min_path=list(p[x+i][y+j])
				except IndexError:
					pass

		if around_value is None:
			print "ERRO",
			for i,j in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)]:
				print (x+i,y+j),
				if(x+i > 0 and y+j>0):
					print ">",(x+i,y+j),
					try:
						if (m[x+i][y+j] is not None) and ((around_value is None) or (m[x+i][y+j]<around_value)):
							around_value=m[x+i][y+j]
					except IndexError:
						pass
			return
					#~ p[x][y].append((x,y))
		if (m[x][y] is None) or (m[x][y] > value+around_value):
			m[x][y]=value+around_value
			self.explode.append((x,y))
			around_min_path.append((x,y))
			p[x][y]=around_min_path
			
		if not (x,y) in self.explored: self.explored.append((x,y))

if __name__=='__main__':
	a=Area(CLEANGRID,0,0)
	
	for x in range(5,10,1):
		for y in range(5,10,1):
			a.setitem(x,y,True)
			
	print a
	a.clear()
	a2=a.getBorder()
	print a2
	a2.clear()
	print a2
